Завдання Варіант № 16 Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:   Кількість точок 1024  Основа ШПФ 2  Прорідження частотне  Частота роботи процесора 1,5 МГц  Розрядність вхідних даних 20 (10+10)  Тип вхідного інтерфейсу, пристрою Зовнішня пам’ять  Тип вихідного інтерфейсу, пристрою CAN   2 Зміст 2. Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 2 2.1. Побудова графа алгоритму ШПФ з основою 2 2 2.2. Біт інверсний порядок видачі даних 4 2.2.1. Блок-схема перетворення 5 3. Розрахунковий розділ 5 4. Розробка функціональної схеми 7 4.1. Вхідний інтерфейс 7 4.2. Вихідний інтерфейс 8 5. Розробка програми 9 2. Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 2.1. Побудова графа алгоритму ШПФ з основою 2 Якщо число N є ступенем 2, то його можна записати як (N/2) * 2; аналогічно N/2 = (M/4) * 2 і т.д. В результаті елементи початкового одновимірного масиву можна розподілити таким чином, щоб елементарними операціями були двохточкові ШПФ. Для побудови графу N-точкового ШПФ з основою 2 потрібно визначити кількість ярусів (Nяр) графу та кількості метеликів (Nм) на кожному ярусі таким чином: Nяр = Log2N, для N=8192, Log28192 = 13; Nм = N/2 = 8192/2= 4096. Граф-алгоритм для 8192 точкового ШПФ за основою 2 показаний на рис. 2. / Рис. 2. Граф алгоритм 16-точкове ШПФ з основою 2 та прорідженням за частотою На рис. 2 кільцям відповідають двохточкові ШПФ, стрілками зображено процедуру множення на повертаючі множники. Елементи пам’яті зображено точками та пронумеровано зверху вниз. Метелик ШПФ показаний на рис. 3, де
Рис. 3. Двохточкове ШПФ (Метелик) X, Y - результати базової операції; А, B - вхідні відліки; WN – повертаючих множники. 2.2. Біт інверсний порядок видачі даних Ще однією особливістю алгоритму з прорідженням за частотою є те, що прямий порядок слідування даних на вході графу змінюється двійково-інверсним на виході. Тому для видачі даних в прямому порядку потрібно здійснити двійково-інверсну перестановку за правилом описаним в табл.1. Таблиця 1. Двійково-інверсна перестановка даних Номер Двійкове представлення Двійкова інверсія Двійково-інверсний номер  0 0000 0000 0  1 0001 1000 8  2 0010 0100 4  3 0011 1100 12  4 0100 0010 2  5 0101 1010 10  6 0110 0110 6  7 0111 1110 14  8 1000 0001 1  9 1001 1001 9  10 1010 0101 5  11 1011 1101 13  … … … …  1021 1111111101 1011111111 383  1022 1111111110 0111111111 511  1023 1111111111 1111111111 1023   2.2.1. Блок-схема перетворення / Рис. 4. Блок-схема алгоритму 8192-точкового перетворення за основою 2 3. Розрахунковий розділ 16 1024 2 F 1,5 20 (10+10) Зовнішня пам'ять CAN    Частота роботи процесора:
, звідси цикл виконання команди:
. base – основа базової операції «метелик»; N – кількість точок вхідного перетворення; base=2 N=1024
– кількість етапів перетворення;
– кількість базових операцій «метелик» на одному етапі;
– кількість базових операцій у всьому перетворенні;


Для виконання базової операції «метелик» необхідно: 4 операцій множення; 6 операцій додавання; 10 операцій читання з пам`яті: - 2*2=4 (для читання дійсної та уявної частини вхідних відліків); - 3*2=6 (для читання дійсної та уявної частини комплексних коефіцієнтів); 4 операцій запису: - 2*2=4 (для запису дійсної та уявної частини вхідних відліків); В результаті на одну базову операцію припадає 24 операцій: Nна 1 мет=24 (оп). Тривалість виконання обчислення ШПФ:
Частота роботи зовнішньої пам’яті(флешка):
, звідси цикл надходження команди:
. Тривалість надходження даних у процесор для обробки: Тнадх=2,5нс– такт надходження даних;
Частота роботи CAN шини:
, звідси цикл надходження команди:
. І оскільки шина CAN опрацьовує по 16 розрядів, необхідно ще помножити на 16. Тривалість виход...